package gold.contest;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC5631 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution_Slide_Window {
        public int maxResult(int[] nums, int k) {
            int cur = 0;
            int res = nums[0];
            for (int i = 0; i < nums.length - 1; ) {
                int step = Math.min(nums.length - 1 - i, k);
                int neg_idx = 0;
                int pos_idx = 0;
                int max = Integer.MIN_VALUE;
                for (int j = 1; j <= step; ++j) {
                    //记录最大值的位置，如果i+1到i+step区间内，值都是非正
                    //后面更新指针的时候，就让指针跳到这个最大值的位置，例如(...,-2,-3,-1,...)就跳到-1的位置
                    if (max < nums[i + j]) {
                        max = nums[i + j];
                        neg_idx = i + j;
                    }
                    //有正的得分，全都要，并且记录最远的正得分的位置
                    if (nums[i + j] > 0) {
                        res += nums[i + j];
                        pos_idx = i + j;
                    }

                }
                //从i+1到i+step中，都没有正的得分，就从这些负的得分中选一个值最大的先跳过去
                if (max <= 0) {
                    //当前已经能够直接跳到最后了，直接跳吧，反正没有正的数了
                    if (i + step == nums.length - 1) {
                        res += nums[nums.length - 1];
                        i = nums.length - 1;
                        break;
                    }
                    res += max;
                    i = neg_idx;
                } else {//有正的得分就跳到i+1到i+step区间中最后一个正的位置
                    i = pos_idx;
                }
            }

            return res;
        }
    }

    class Solution {
        public int maxResult(int[] nums, int k) {
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            int maxIndex = 0;

            for (int i = 1; i < nums.length; i++) {
                int curMax = Integer.MIN_VALUE;
                if (maxIndex >= i - k) curMax = dp[maxIndex];
                else for (int j = i - 1; j >= 0 && j >= i - k; j--) {
                    curMax = Math.max(curMax, dp[j]);
                }
                dp[i] = nums[i] + curMax;
                if (dp[i] > dp[maxIndex]) maxIndex = i;
            }

            return dp[nums.length - 1];
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,-5,-20,4,-1,3,-6,-3]");
        System.out.println(solution.maxResult(arr, 2));
    }

    public static void main(String[] args) throws Exception {
        LC5631 an = new LC5631();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
